#ifndef GRATE_UTIL_COMPACT_QUEUE_H
#define GRATE_UTIL_COMPACT_QUEUE_H

#include <string>
#include "common.h"
#include "word.h"

namespace growth_rate {

// CompactQueue is a generic data structure used to hold words.
// Each letter (item) added to the queue is packed as a sequence of bits
// of fixed length. CompactQueue is implemented as a cyclic queue.
class CompactQueue {
 public:
  // REQUIRES: capacity_in_bytes > 0
  //           1 <= item_size_in_bits <= 8
  CompactQueue(size_t capacity_in_bytes, size_t item_size_in_bits);
  virtual ~CompactQueue() {
    FreeArray(&buffer_);
  }

  size_t get_capacity_in_bytes() const;
  size_t get_capacity_in_items() const;
  bool is_empty() const;
  size_t get_size_in_bytes() const;
  size_t get_size_in_items() const;

  // Returns true if the item was successfully added, or false if the
  // queue is full.
  bool push_item(uint8_t item);
  // Push all items in word into the queue. Return the number of items
  // that were actually pushed.
  size_t push_word(const Word &word);
  // REQUIRES: !is_empty()
  uint8_t peek_item() const;
  // REQUIRES: !is_empty()
  uint8_t pop_item();
  // Pops the requested amount of items in the buffer and return it as word.
  // REQUIRES: queue has at least "length" items.
  Word pop_word(uint8_t *buffer, size_t length);

  // Dump at most @max_size first elements from the queue (don't
  // actually remove them from the queue). Return the number of
  // elements dumped. Use for debug purposes only.
  size_t dump_to_array(uint8_t *array, size_t max_size) const;
  // Dump queue in a human-readable form.
  std::string dump() const;

 private:
  // Helper routine to move bit pointers in a cyclic queue.
  void shift_bit_pos(size_t *bit_pos) const;
  // Unpack an item of item_size_in_bits_ bits, starting from @bit_pos.
  uint8_t get_item_at_bit_pos(size_t bit_pos) const;
  // Pack @item of item_size_in_bits_ bits, starting from @bit_pos.
  void put_item_at_bit_pos(uint8_t item, size_t bit_pos);

  const size_t capacity_in_bytes_;
  const size_t item_size_in_bits_;

  uint8_t *buffer_;      // Buffer holding the items.
  size_t num_of_items_;  // Number of items currently in the queue
                         // (stored explicitly just for convenience).
  size_t head_bit_pos_;  // Number of first bit of head item
                         // of the queue. Lies in [0, 8 * capacity_in_bytes_).
  size_t tail_bit_pos_;  // Number of first bit after tail item
                         // of the queue. Lies in [0, 8 * capacity_in_bytes_).
};

// IncreasingLengthWordQueue is a special-purpose CompactQueue usable for
// iterating over words in the order of increasing length. At any moment, the
// queue may only contain words of length L and (L+1) for some value of L.
class IncreasingLengthWordQueue {
 public:
  // REQUIRES: capacity_in_bytes > 0
  //           1 <= item_size_in_bits <= 8
  IncreasingLengthWordQueue(size_t capacity_in_bytes,
                            size_t item_size_in_bits)
    : queue_(capacity_in_bytes, item_size_in_bits),
      shorter_words_(0),
      longer_words_(0),
      word_length_(0) { }

  bool is_empty() const { return queue_.is_empty(); }
  size_t head_word_length() const {
    CHECK_GT(shorter_words_, 0);
    return word_length_;
  }
  size_t get_size_in_bytes() const { return queue_.get_size_in_bytes(); }

  // Pops the first word in the queue and stores it in the buffer.
  // and return it as word. If buffer is too short, returns empty word.
  Word pop_word(uint8_t *buffer, size_t buffer_size);
  // Adds the word in the queue. Fails if queue size is too small.
  void push_word(const Word &word);

 private:
  CompactQueue queue_;
  size_t shorter_words_;  // Number of words of length L.
  size_t longer_words_;  // Number of words of length (L+1).
  size_t word_length_;  // Length of a shortest word.
};

}  // namespace growth_rate

#endif  // GRATE_UTIL_COMPACT_QUEUE_H
